1. Field of the Invention
The invention relates generally to the classification of data packets, and more specifically to the classification of data packets using structures that contain multiple classes.
2. Background Information
In a communications network, there is a well-recognized need to classify information units, such as packets, that are passed between the various network devices (e.g., routers and switches) in the network, in order to support a wide range of applications, such as security control, Class of Service (CoS) and Quality of Service (QoS). Often, in such networks, network devices use access control lists (ACLs) to classify packets for these applications.
An ACL typically comprises an ordered list of rules where each rule defines a pattern (criterion) that is compared against received packets. The pattern could specify a particular source or destination address, a protocol or some other field that is looked for in the packet. For example, the pattern might be defined to look for a specific protocol in the packet's header such as, the Transmission Control Protocol (TCP). The pattern is used to determine if the rule applies to the packet. If the pattern is found in the packet, the rule is said to apply to the packet.
Associated with each rule is an action that specifies the act to be taken if the rule applies. In its simplest form, this action may be to allow the matched packet to proceed towards its destination (i.e., “permit”) or to stop the packet from proceeding any further (i.e., “deny”). Conversely, if there is no match to any of the ACL's rules, the action may be to drop the packet (i.e., “a final deny”). In a more sophisticated form, complex policies and filtering rules may be implemented in the ACL to determine the course of the data packet.
Network devices, such as routers or switches, originally have used ACLs for packet filtering, however, as new services, such as QoS and CoS, have been implemented on these devices ACL use has been extended to support these services, as well. But, as algorithms and features have been developed for these services, the classification and action parameters associated with rules contained in an ACL tend to be defined specifically for a particular algorithm or feature associated with the service, rather than for an overall policy that may be associated with the service. To correct this, network devices often include structures that enable packet classification to be specified separately from policy. Two such structures include the class map and the policy map.
A class map is a structure that is used to define a particular packet classification or class. A class map typically comprises a class criterion and one or more match statements. The class criterion usually defines some condition, such as “match any of the following rules” or “match all of the following rules,” that applies to the overall class map.
The match statement may specify an individual pattern or an entire ACL. If the packet meets the criterion associated with the class, the class is said to apply to that packet.
A policy map is a structure that is used to define the policy parameters or algorithms to be applied to a classified packet. A policy map typically includes one or more classes and one or more action statements associated with each class. The action statements associated with a particular class are performed, if the class applies to the packet being processed.
Typically, a packet is processed by searching for the first class that applies to the packet. The number of match statements involved and the amount of processing time needed to make this determination often depends on the approach taken. For example, one approach would be to run through the list of classes in the policy map starting from the first class in the list and continuing towards the last class in the list until a class is found to apply to the packet. This approach is simple, but is not very efficient. Packets that meet the criteria associated with classes earlier in the list will be processed faster than packets that meet criteria associated with classes that are positioned farther down the list, thus the time it takes to process various packets may vary.
It would be desirable to have a technique that can classify a packet in accordance with a multi-class policy in a manner that is faster than a sequential search and that can complete the processing in a deterministic amount of time regardless of the number of classes in the policy.